package first.niuke.midding;

/**
 * @ClassName NC21
 * @description:
 * @author: 荣燊
 * @create: 2021-06-22 10:01
 **/
public class NC21 {
    // 链表内指定区间反转
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // write code here
        // 伪节点dummy,与pre
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;

        // pre指向要反转子链表头部的前驱节点
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }

        // head指向反转子链表的首部
        head = pre.next;
        ListNode next;

        for (int i = n; i < m; i++) {
            // 这里的逻辑？？？

        }

        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next = null;
    }

    // 递归实现反转链表
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    // 普通实现反转链表
    public ListNode reverse1(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        // 第一步将pre节点空出来，第二再来赋值
        while (head != null) {
            next = head.next;
            // 第一次执行时是空，之后再执行就是反转了
            head.next = pre;
            pre = head;
            head = next;
        }
        // 注意返回值
        return pre;
    }
}
